package leetcode;

import java.util.*;


/**
 * 力扣算法练习工具类
 * <a href="https://leetcode.cn/problems/binary-search/">...</a>
 💗💗💗  双指针算法口诀
        小口诀1 左右指针：结果比目标，小了要变大，左针右移+
                       结果比目标，大了要变小，右针左移-
        小口诀2 前后指针：快慢相等值不变，慢针不动快针走;
                       快慢不等值，我是题型1，慢针向前一步走，快针赋值给慢针，快针向前一步走
                       快慢不等值，我是题型2，快针赋值给慢针，慢针向前一步走，快针向前一步走
*/
public class LeetCodeUtils {

    /**
     1、两数之和
     给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
     你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
     你可以按任意顺序返回答案。
     示例 1：
     输入：nums = [2,7,11,15], target = 9
     输出：[0,1]
     解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
     小口诀1 左右指针：结果比目标，小了要变大，左针右移+
     结果比目标，大了要变小，右针左移-
     */
    public int[] twoSum1(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int result = target - nums[i];
            if (map.containsKey(result)) {
                return new int[]{map.get(result),i};
            }
            map.put(nums[i],i);
        }
        return null;
    }
    /*
        两数之和 暴力破解
     */
    public int[] twoSumFor1(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i,j};
                }
            }
        }
        return null;
    }

    /**
     * 167. 两数之和 II - 输入有序数组
     * 给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。
     * 如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
     * 以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
     * 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
     * 你所设计的解决方案必须只使用常量级的额外空间。
     * 示例 1：
     * 输入：numbers = [2,7,11,15], target = 9
     * 输出：[1,2]
     * 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
     * 小口诀1 左右指针：结果比目标，小了要变大，左针右移+
     *                        结果比目标，大了要变小，右针左移-
     */
    public int[] twoSum167(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            if ((numbers[left] + numbers[right]) > target) {
                right--;
            }else if ((numbers[left] + numbers[right]) < target){
                left++;
            }else {
                return new int[]{left+1,right+1};
            }
        }
        return null;
    }

    /**
     * 344. 反转字符串
     * 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
     * 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
     * 示例 1：
     * 输入：s = ["h","e","l","l","o"]
     * 输出：["o","l","l","e","h"]
     * 小口诀1 左右指针：结果比目标，小了要变大，左针右移+
     *                        结果比目标，大了要变小，右针左移-
     */
    public void reverseString344(char[] s) {
        int left = 0;
        int right = s.length-1;
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
    public  void reverseString(char[] s) {
        for (int i = 0,j = s.length - 1; i < j; i++,j--) {
            //左指针赋值临时变量
            char temp = s[i];
            //右指针赋值左指针
            s[i] = s[j];
            s[j] = temp;
        }
    }

    /**
     * 704. 二分查找
     * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
     * 示例 1:
     * 输入: nums = [-1,0,3,5,9,12], target = 9
     * 输出: 4
     * 解释: 9 出现在 nums 中并且下标为 4
     * 小口诀1 左右指针：结果比目标，小了要变大，左针右移+
     *                        结果比目标，大了要变小，右针左移-
     */
    public int searchFor704(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }
    public int searchWhile704(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            if (nums[left] == target) {
                return left;
            }
            if (nums[right] == target) {
                return right;
            }
            left++;
            right--;
        }
        return -1;
    }
    public int search704(int[] nums, int target) {
       int left = 0, right = nums.length-1;
       while (left <= right) {
           int middle = (left + right) / 2;
           if (nums[middle] == target) {
               return middle;
           }else if (nums[middle] < target) {
               left = middle + 1;
           }else if (nums[middle] > target) {
               right = middle - 1;
           }
       }
        return -1;
    }


    /**
     * 26. 删除有序数组中的重复项
     * 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
     * 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
     * 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
     * 返回 k 。
     * 示例 1：
     * 输入：nums = [1,1,2]
     * 输出：2, nums = [1,2,_]
     * 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
     * 小口诀2 前后指针：快慢相等值不变，慢针不动快针走;
     *                        快慢不等值，我是题型1，慢针向前一步走，快针赋值给慢针，快针向前一步走
     *                        快慢不等值，我是题型2，快针赋值给慢针，慢针向前一步走，快针向前一步走
     */
    public  int removeDuplicates26(int[] nums) {
        int left = 0, right = 0;
       while (right < nums.length) {
           if (nums[left] != nums[right]) {
               left++;
               nums[left] = nums[right];
           }
           right++;
       }
        return left + 1;
    }

    /**
     * 283. 移动零
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     * 示例 1:
     * 输入: nums = [0,1,0,3,12]
     * 输出: [1,3,12,0,0]
     * 小口诀2 前后指针：快慢相等值不变，慢针不动快针走;
                      快慢不等值，我是题型1，慢针向前一步走，快针赋值给慢针，快针向前一步走
、                    快慢不等值，我是题型2，快针赋值给慢针，慢针向前一步走，快针向前一步走
     */
    public static void moveZeroes283(int[] nums) {
        int left = 0,right = 0;
        while (right < nums.length) {
            if (nums[right] !=  0) {
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
                left++;
            }
            right++;
        }
    }

    /**
     * 27. 移除元素
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
     * 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
     * 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
     * 返回 k。
     * 示例 1：
     * 输入：nums = [3,2,2,3], val = 3
     * 输出：2, nums = [2,2,_,_]
     * 解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
     * 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
     * 小口诀2 前后指针：快慢相等值不变，慢针不动快针走;
     *                快慢不等值，我是题型1，慢针向前一步走，快针赋值给慢针，快针向前一步走
     *                快慢不等值，我是题型2，快针赋值给慢针，慢针向前一步走，快针向前一步走
     */
    public static int removeElement27(int[] nums, int val) {
        int left = 0,right = 0;
        while (right < nums.length) {
            if (nums[right] != val) {
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
                left++;
            }
            right++;
        }
        return left;
    }
    public static int removeElementD27(int[] nums, int val) {
        int left = 0,right = 0;
        while (right < nums.length) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
            right++;
        }
        return left;
    }


    /**
     * 11. 盛最多水的容器
     * 输入：[1,8,6,2,5,4,8,3,7]
     * 输出：49
     * 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
     * min(8,7) * 7 = 49
     * 小口诀1 左右指针：结果比目标，小了要变大，左针右移+
     *                结果比目标，大了要变小，右针左移-
     */
    public static int maxArea11(int[] height) {
        int result = 0;
        int left = 0,right = height.length-1;
        while (left < right) {
            int max;
            //指针右移
            if (height[left] < height[right]) {
                max = height[left] * (right -left);
                left++;
            }else {
                max = height[right] * (right -left);
                //指针左移
                right--;
            }
            if (max > result) {
                result = max;
            }
        }
        return result;
    }

    /**
     * 15. 三数之和
     * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
     * 注意：答案中不可以包含重复的三元组。
     * 示例 1：
     * 输入：nums = [-1,0,1,2,-1,-4]
     * 输出：[[-1,-1,2],[-1,0,1]]
     * 解释：
     * nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
     * nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
     * nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
     * 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
     * 注意，输出的顺序和三元组的顺序并不重要。
     小口诀1 左右指针：结果比目标，小了要变大，左针右移+
                    结果比目标，大了要变小，右针左移-
     */
    public static List<List<Integer>> threeSum15(int[] nums) {
        if (nums == null || nums.length < 3) {
            return new ArrayList<>();
        }
        Set<List<Integer>> result = new HashSet<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int left = i + 1,right = nums.length-1;
            while (left < right) {
                if (nums[left] + nums[right] == -nums[i]) {
                    result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    right--;
                }else if (nums[left] + nums[right] > -nums[i]) {
                    right--;
                }else {
                    left++;
                }
            }
        }
        return new ArrayList<>(result);
    }


    /**
     *42. 接雨水
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     * 示例 1：
     * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
     * 输出：6
     * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
     * [3]
     */
    public static int trap42(int[] height) {
        int result = 0;
        int left = 0,right = height.length-1;
        int leftMax = 0,rightMax = 0;
        while (left < right) {
            if (leftMax < height[left]) {
                leftMax = height[left];
            }
            if (rightMax < height[right]) {
                rightMax = height[right];
            }
            if (height[left] < height[right]) {
                result += leftMax -height[left];
                ++left;
            }else {
                result += rightMax - height[right];
                --right;
            }
        }
        return result;

    }


    public static void main(String[] args) {
        int[] arr = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        trap42(arr);
        System.out.println();
    }
}
